package com.lx.algorithm.LinkedList;

import java.util.Stack;

/**
 * Description: 链表小练习
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-20 08:10:27
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-20     张李鑫                     1.0         1.0 Version
 */
public class MyLinkedList {
    /**
     * 实现一个链表 如果是奇数个 返回一个中点 偶数就返回第一个终点
     * 实现一个链表 如果是奇数个 返回一个中点 偶数就返回第二个终点
     * <p>
     * 实现一个链表 如果是奇数个 返回中点前一个节点 偶数就返回第一个中点的前一个节点
     * 实现一个链表 如果是奇数个 返回一个中点 偶数就返回第二个终点
     */


    public static class Node {
        private Node next;
        private Integer value;

        public Node(Integer value) {
            this.value = value;
        }
    }

    /**
     * <p>
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * </p>
     *
     * @param
     * @return com.lx.algorithm.LinkedList.MyLinkedList.Node
     * @Author zlx
     * @date 2021/9/20
     */
    public static Node getMidFirst(Node head) {
        if (null == head) {
            return null;
        }
        Node p = head;
        Node p1 = head;

        while (null != p1.next && null != p1.next.next) {
            p = p.next;
            p1 = p1.next.next;
        }
        return p;
    }

    /**
     * <p>
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * </p>
     *
     * @param head
     * @return com.lx.algorithm.LinkedList.MyLinkedList.Node
     * @Author zlx
     * @date 2021/9/20
     */
    public static Node getMidSecond(Node head) {
        if (null == head) {
            return null;
        }
        Node p = head;
        Node p1 = head;

        while (null != p1.next.next) {
            p1 = p1.next;
            p = p.next.next;
        }
        return p.next;
    }

    /**
     * <p>
     * 不使用额外的空间复杂度
     * </p>
     *
     * @param node
     * @return boolean
     * @Author zlx
     * @date 2021/9/20
     */
    public static boolean isAbbA(Node node) {
        //首先找中间点 如果是偶数返回后一个节点
        Node midSecond = getMidFirst(node);
        //单链表反转
        Node change = change(midSecond.next);

        Node head = node;
        Node head1 = change;

        midSecond.next = null;
        boolean flag = true;
        while (head != null && head1 != null) {
            if (node.value != change.value) {
                flag = false;
                break;
            }
            head = head.next;
            head1 = head1.next;
        }
        Node change1 = change(head1);
        midSecond.next = change1;
        return flag;
    }


    /**
     * <p>
     * 单链表反转
     * </p>
     *
     * @param node
     * @return com.lx.algorithm.LinkedList.MyLinkedList.Node
     * @Author zlx
     * @date 2021/9/20
     */
    public static Node change(Node node) {
        if (null == node) {
            return null;
        }
        Node old = null;
        Node newNode = null;
        while (null != node) {
            //获取下一个节点
            newNode = node.next;
            //把老节点断链
            node.next = old;
            //老节点变成当前节点
            old = node;
            //当前节点变成当前节点的下一个节点
            node = newNode;
        }
        return old;
    }


    /**
     * <p>
     * 使用额外的空间复杂度
     * </p>
     *
     * @param node
     * @return boolean
     * @Author zlx
     * @date 2021/9/20
     */
    public static boolean isAbbAByHashMap(Node node) {
        Stack<Node> nodes = new Stack<>();
        Node head = node;
        while (null != head) {
            nodes.push(head);
            head = head.next;
        }
        while (!nodes.isEmpty()) {
            Node pop = nodes.pop();
            boolean flag = pop.value == node.value;
            if (!flag) {
                return false;
            }
            node = node.next;

        }
        return true;
    }

    public static void main(String[] args) {
        Node node2 = new Node(53);
        Node node3 = new Node(54);
        Node node4 = new Node(54);
        Node node5 = new Node(53);


        node2.next = node3;
        node3.next = node4;
        node4.next=node5;

        System.out.println( isAbbA(node2));
    }
}